#ifndef __BWLIB_NUMBER_THEORY_CHINA_REMAINDER_THEOREM
#define __BWLIB_NUMBER_THEORY_CHINA_REMAINDER_THEOREM
#include "../config.h"
#include "congruence_equation.h"
#include "module.h"
#include <iterator>

namespace bwlib
{
	/* @brief: 解线性同余方程组
	 *          x = ci (mod pi), 1 <= i <= n
	 *         其中 p 要求是素数
	 * @complexity: O(n logn)
	 * @param: c,     BidirectionalIterator
	 *         p,     BidirectionalIterator
	 *         p_end, BidirectionalIterator
	 * @return: x, 0 <= x < product(pi), 1 <= i <= n
	 */
	template<typename Iter>
	typename std::iterator_traits<Iter>::value_type
		china_remainder_theorem(Iter c, Iter p, Iter p_end)
	{
		typedef typename std::iterator_traits<Iter>::value_type value_type;
		value_type product = 1;
		for(Iter p_beg = p; p_beg != p_end; ++p_beg)
		{
#ifdef __BWLIB_SAFER_CHECK
			if(*p_beg <= 0) 
				throw std::runtime_error("module a negative number");
#endif
			product *= *p_beg;
		}

		value_type answer = 0, temp;
		Iter c_beg = c;
		Iter p_beg = p;
		while(p_beg != p_end)
		{
			temp = product / *p_beg;
			temp *= linear_congruence_equation(temp, *c_beg, *p_beg);
#ifdef __BWLIB_SAFER_CHECK
			if(temp < 0) 
				throw std::runtime_error("p might not a prime number");
#endif
			answer = (answer + temp) % product;
			++c_beg, ++p_beg;
		}

		return answer;
	}
}

#endif
